#include <iostream>
#include <memory>
#include <random>
#include <vector>
using namespace std;

const int inf = 0x3f3f3f3f;

class Treap {
   public:
    struct Node {
        int val;
        int w, siz;
        shared_ptr<Node> ch[2];  // for left and right children
    };
    using NodePtr = shared_ptr<Node>;

   public:
    void Insert(int x) { Insert(head.ch[0], x); }
    void Erase(int x) { Erase(head.ch[0], x); }
    // return the amount of node whose value is less than x
    int GetRank(int x) {
        auto u = head.ch[0];
        int lsiz = 0;
        while (u) {
            if (x > u->val) lsiz += u->ch[0]->siz + 1;
            u = u->ch[x > u->val];
        }
        return lsiz;
    }
    // return the value of the k-min node
    int get_val(int rk) {
        auto u = head.ch[0];
        while (u) {
            int now_rk = u->ch[0]->siz + 1;
            if (rk == now_rk) return u->val;  // find
            u = u->ch[rk > now_rk];
            if (rk > now_rk) rk -= now_rk;
        }
        return 0;
    }
    // return the max value in a set whose element is less than x
    int get_pre(int x) {
        auto u = head.ch[0];
        int ret = -inf;
        while (u) {
            if (x > u->val) ret = max(ret, u->val);
            u = u->ch[x > u->val];
        }
        return ret;
    }
    // return the min value in a set whose element is more than x
    int get_nex(int x) {
        auto u = head.ch[0];
        int ret = inf;
        while (u) {
            if (x < u->val) ret = min(ret, u->val);
            u = u->ch[x >= u->val];
        }
        return ret;
    }

    // void show(int p = root, int dep = 1) {
    //     if (p == 0) return;
    //     show(ch[p][0], dep + 1);
    //     printf("|| val: %d, deep: %d, siz: %d, p: %d\n", pool[p].val, dep, pool[p].siz, p);
    //     show(ch[p][1], dep + 1);
    // }

   private:  // kernel
    NodePtr Insert(NodePtr &u, int x) {
        if (u == 0) return u = NewNode(x);
        int dir = x > u->val;
        auto ret = Insert(u->ch[dir], x);
        if (u->ch[dir]->w > u->w) Rotate(u, dir ^ 1);
        PushUp(u);
        return ret;
    }

    NodePtr Erase(NodePtr &u, int x) {
        if (u == nullptr) return nullptr;
        if (u->val != x) {
            int dir = x > u->val;
            auto ret = Erase(u->ch[dir], x);
            if (ret) PushUp(u);
            return ret;
        }
        // the target node is u
        auto ret = u;
        if (u->ch[0] == nullptr || u->ch[1] == nullptr) {
            u = u->ch[0] ? u->ch[0] : u->ch[1];
        } else {
            // rotate, then erase
            int dir = (u->ch[1]->w > u->ch[0]->w);
            Rotate(u, dir ^ 1);
            Erase(u->ch[dir ^ 1], x);
            PushUp(u);
        }
        return ret;
    }

   private:  // utility
    // return a rand number
    inline int rd() {
        static std::random_device d;               // 硬件随机数
        static std::default_random_engine e(d());  // 随机数引擎，传入种子
        return e();                                // 输出引擎产生的随机数
    }
    // return a new node within value x
    inline shared_ptr<Node> NewNode(int x) {
        return make_shared<Node>(x, rd(), 1, nullptr, nullptr);
    }
    // calculate the size of the subtree u
    inline void PushUp(NodePtr u) {
        u->siz = u->ch[0]->siz + u->ch[1]->siz + 1;
    }
    // rotate the subtree u by dir
    inline void Rotate(NodePtr &u, int dir) {
        auto v = u->ch[dir ^ 1];
        u->ch[dir ^ 1] = v->ch[dir], PushUp(u);
        v->ch[dir] = u, PushUp(v), u = v;
    }

   private:
    Node head;
};

int main() {
    // int a  = 1;
    // int* x = nullptr;
    // int* y = &a;
    // cout << (x | y);
}
